package com.sise.Linked;

/**
 *      142. 环形链表 II
 *
 *      给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。
 *      为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 *      说明：不允许修改给定的链表。
 *      进阶：
 *      你是否可以使用 O(1) 空间解决此题？
 *
 *      根据：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-jian-hua-gong-shi-jia-2/
 *      slow = x + y
 *      fast = x + y + n(y + z)                 n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数
 *      (x + y) * 2 = x + y + n (y + z)         fast指针走过的节点数 = slow指针走过的节点数 * 2
 *      x + y = n (y + z)                       两边消掉一个 (x + y)
 *      x = n (y + z) - y
 *      x = (n - 1) (y + z) + z                 在从 n(y+z) 中提出一个 （y+z）来，整理公式之后为如下公式
 *      x = z                                   当 n = 1时
 *
 *
 *      解题思路：分两个步骤，首先通过快慢指针的方法判断链表是否有环；接下来如果有环，则寻找入环的第一个节点。
 *      具体的方法为，首先假定链表起点到入环的第一个节点A的长度为a【未知】，到快慢指针相遇的节点B的长度为（a + b）【这个长度是已知的】。
 *      现在我们想知道a的值，注意到快指针p2始终是慢指针p走过长度的2倍，所以慢指针p从B继续走（a + b）又能回到B点，如果只走a个长度就能回到节点A。
 *      但是a的值是不知道的，解决思路是曲线救国，注意到起点到A的长度是a，那么可以用一个从起点开始的新指针q和从节点B开始的慢指针p同步走，相遇的地方必然是入环的第一个节点A。
 *
 */
public class _142_detectCycle {

    public ListNode detectCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;
        while (true){
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}
